#leetcode题目70：爬楼梯
#难度：简单

#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：动态规划

from typing import List
class Solution:
    def climbStairs(self, n: int) -> int:
        if n==1:
            return 1
        if n==2:
            return 2
        dp=[0]*(n+1)
        dp[1]=1
        dp[2]=2
        for i in range(3,n+1):
            dp[i]=dp[i-1]+dp[i-2]#前两个状态累计而来
        return dp[n]

#测试数据
n=2
#预期输出：2
solution=Solution()
print(solution.climbStairs(n))

n=3
#预期输出：3
solution=Solution()
print(solution.climbStairs(n))